#include<bits/stdc++.h>
#define int long long
#define il inline
#define ct const
#define dl double
#define pk push_back
#define fi first
#define se second
#define pii pair<int,int>
#define N 60
using namespace std;
il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
	}
	return x*f;
}
char f__[40];
il void write(int x){
	int cnt=0;
	if(x<0){
		putchar('-');x=-x;
	}
	if(!x) putchar('0');
	while(x){
		f__[cnt++]=x%10+'0';x/=10;
	}
	while(cnt) putchar(f__[--cnt]);
}
int Q,dp[N][N*N<<1],mx=50,f[N][N],mod;
il void Add(int &a,int b){
    a=a+b>=mod?a+b-mod:a+b;
}
il int Pow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;b>>=1;
    }
    return res;
}
signed main(){
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
    mod=read();Q=read();
    for(int m=0;m<=mx;++m){
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int n=0;n<=mx;++n){
            for(int i=0;i<=n*m;++i) if(dp[n][i]){
                for(int k=0;k<=m;++k){
                    Add(dp[n+1][abs(i-k)],dp[n][i]*(m-k+1)%mod);
                    Add(dp[n+1][i+k],dp[n][i]*(m-k+1)%mod);
                }
                // cerr<<m<<" "<<n<<" "<<i<<" "<<dp[n][i]<<"\n";
            }
            f[m][n]=dp[n][0]*Pow(2,mod-2)%mod;
        }
    }
    // int n=3,m=4;
    // cerr<<Pow(m+1,n<<1)*675356228ll%mod<<"\n";
    while(Q--){
        int n=read(),m=read();
        int tmp=Pow(m+1,n<<1);
        // cerr<<tmp<<" "<<f[m][n]<<"\n";
        write((tmp-f[m][n]+mod)%mod*Pow(tmp*2%mod,mod-2)%mod);putchar('\n');
    }
	return 0;
}